package Luogu;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class P1060 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String tmp = br.readLine();
        int V = Integer.parseInt(tmp.split(" ")[0]);
        int n = Integer.parseInt(tmp.split(" ")[1]);
        int[] ws = new int[n + 1];
        int[] vs = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            tmp = br.readLine();
            ws[i] = Integer.parseInt(tmp.split(" ")[0]);
            vs[i] = ws[i] * Integer.parseInt(tmp.split(" ")[1]);
        }
        long[][] dp = new long[2][V + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                if (ws[i] <= j) {
                    dp[i%2][j] = Math.max(dp[(i - 1) % 2][j], dp[(i - 1) % 2][j - ws[i]] + vs[i]);
                } else {
                    dp[i%2][j] = dp[(i - 1) % 2][j];
                }
            }
        }
        System.out.println(dp[n%2][V]);
    }

    public static int process(int index, int rest, int[] ws, int[] vs) {
        if (index == 0)
            return 0;
        if (ws[index] <= rest) {
            return Math.max(process(index - 1, rest, ws, vs), process(index - 1, rest - ws[index], ws, vs) + vs[index]);
        } else {
            return process(index - 1, rest, ws, vs);
        }
    }
}
